fn sieve(limit: usize) -> Vec<usize> {
    let mut c = vec![false; limit + 1];
    let mut p = 3;
    loop {
        let p2 = p * p;
        if p2 > limit {
            break;
        }
        (p2..=limit).step_by(2 * p).for_each(|i| c[i] = true);
        loop {
            p += 2;
            if !c[p] {
                break;
            }
        }
    }
    let mut two: Vec<usize> = vec![2];
    two.drain(0..1)
        .chain(
            c.iter()
                .enumerate()
                .skip(3)
                .step_by(2)
                .filter_map(|(i, composite)| if *composite { None } else { Some(i) }),
        )
        .collect()
}

fn square_free(from: u64, to: u64) -> Vec<u64> {
    let limit = ((to as f64).sqrt()) as usize;
    let primes = sieve(limit);
    (from..=to)
        .filter(|i| {
            primes
                .iter()
                .map(|p| *p as u64)
                .map(|p| p.pow(2))
                .take_while(|p2| *p2 <= *i)
                .all(|p2| *i % p2 != 0)
        })
        .collect()
}

const TRILLION: u64 = 1000000000000;
fn main() {
    println!("Square-free integers from 1 to 145:");
    let sf = square_free(1, 145);
    sf.iter().enumerate().for_each(|(i, n)| {
        if i > 0 && i % 20 == 0 {
            println!();
        }
        print!("{:4}", n);
    });

    println!(
        "\n\nSquare-free integers from {} to {}",
        TRILLION,
        TRILLION + 145
    );
    let sf = square_free(TRILLION, TRILLION + 145);
    sf.iter().enumerate().for_each(|(i, n)| {
        if i > 0 && i % 5 == 0 {
            println!();
        }
        print!("{:14}", n);
    });

    println!("\n\nNumber of square-free integers:");
    (2..7).map(|i| (10_u64).pow(i)).for_each(|n| {
        println!("  from 1 to {} = {}", n, square_free(1, n).len());
    });
}

#[test]
fn test() {
    assert_eq!(
        square_free(1, 145),
        vec![
            1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35,
            37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71,
            73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105,
            106, 107, 109, 110, 111, 113, 114, 115, 118, 119, 122, 123, 127, 129, 130, 131, 133,
            134, 137, 138, 139, 141, 142, 143, 145
        ]
    );

    assert_eq!(
        square_free(TRILLION, TRILLION + 145),
        vec![
            1000000000001,
            1000000000002,
            1000000000003,
            1000000000005,
            1000000000006,
            1000000000007,
            1000000000009,
            1000000000011,
            1000000000013,
            1000000000014,
            1000000000015,
            1000000000018,
            1000000000019,
            1000000000021,
            1000000000022,
            1000000000023,
            1000000000027,
            1000000000029,
            1000000000030,
            1000000000031,
            1000000000033,
            1000000000037,
            1000000000038,
            1000000000039,
            1000000000041,
            1000000000042,
            1000000000043,
            1000000000045,
            1000000000046,
            1000000000047,
            1000000000049,
            1000000000051,
            1000000000054,
            1000000000055,
            1000000000057,
            1000000000058,
            1000000000059,
            1000000000061,
            1000000000063,
            1000000000065,
            1000000000066,
            1000000000067,
            1000000000069,
            1000000000070,
            1000000000073,
            1000000000074,
            1000000000077,
            1000000000078,
            1000000000079,
            1000000000081,
            1000000000082,
            1000000000085,
            1000000000086,
            1000000000087,
            1000000000090,
            1000000000091,
            1000000000093,
            1000000000094,
            1000000000095,
            1000000000097,
            1000000000099,
            1000000000101,
            1000000000102,
            1000000000103,
            1000000000105,
            1000000000106,
            1000000000109,
            1000000000111,
            1000000000113,
            1000000000114,
            1000000000115,
            1000000000117,
            1000000000118,
            1000000000119,
            1000000000121,
            1000000000122,
            1000000000123,
            1000000000126,
            1000000000127,
            1000000000129,
            1000000000130,
            1000000000133,
            1000000000135,
            1000000000137,
            1000000000138,
            1000000000139,
            1000000000141,
            1000000000142,
            1000000000145
        ]
    );
}
